///\todo upgrade

//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_CONTAINER_CINTRUSIVERBTREE_H_
#define _BUOLA_CONTAINER_CINTRUSIVERBTREE_H_

#include <buola/buola.h>
#include <buola/io.h>
#include <buola/container/detail/csizeholder.h>
#include <buola/iterator/facade.h>
#include <buola/utility/upointerplusbits.h>
#include <buola/utility/umemberasbase.h>

namespace buola {

namespace detail {

    template<typename tPointer>
    struct CRBTreeNode
    {
        tPointer mParent,mLeft,mRight;
        bool mRed;

        const tPointer &GetParent() const   {   return mParent;     }
        const tPointer &GetLeft() const     {   return mLeft;       }
        const tPointer &GetRight() const    {   return mRight;      }
        bool GetRed() const                 {   return mRed;        }

        void SetParent(const tPointer &pParent)     {   mParent=pParent;    }
        void SetLeft(const tPointer &pLeft)         {   mLeft=pLeft;        }
        void SetRight(const tPointer &pRight)       {   mRight=pRight;      }
        void SetRed(bool pRed)                      {   mRed=pRed;          }

        void Init(const tPointer &pParent,bool pRed)
        {
            mParent=pParent;
            mLeft=nullptr;
            mRight=nullptr;
            mRed=pRed;
        }
    };

    template<typename tPointer>
    struct CRBTreeCompactNode
    {
        UPointerPlusBits<tPointer,1> mParent;
        tPointer mLeft,mRight;

        tPointer GetParent() const          {   return mParent.GetPointer();    }
        const tPointer &GetLeft() const     {   return mLeft;                   }
        const tPointer &GetRight() const    {   return mRight;                  }
        bool GetRed() const                 {   return mParent.GetBits();       }

        void SetParent(const tPointer &pParent)     {   mParent.SetPointer(pParent);    }
        void SetLeft(const tPointer &pLeft)         {   mLeft=pLeft;                    }
        void SetRight(const tPointer &pRight)       {   mRight=pRight;                  }
        void SetRed(bool pRed)                      {   mParent.SetBits(pRed?1:0);      }

        void Init(const tPointer &pParent,bool pRed)
        {
            mParent.SetPointerAndBits(pParent,pRed?1:0);
            mLeft=nullptr;
            mRight=nullptr;
        }
    };

/*namespace detail*/ }

/// The class template rbtree is an intrusive red-black tree container, that
/// is used to construct intrusive set and multiset containers. The no-throw
/// guarantee holds only, if the value_compare object
/// doesn't throw.
///
/// The template parameter \c T is the type to be managed by the container.
/// The user can specify additional options and if no options are provided
/// default options are used.
///
/// The container supports the following options:
/// \c base_hook<>/member_hook<>/value_traits<>,
/// \c constant_time_size<>, \c size_type<> and
/// \c compare<>.

template<typename tKey,bool vConstTimeSize=true,typename tCompare=std::less<tKey>,typename tPointer=tKey*>
class CIntrusiveRBTree : public UUncopiable
{
    typedef ORebindPointer<tPointer,const CIntrusiveRBTree> tTreePointer;

public:
    typedef ORebindPointer<tPointer,tKey> pointer;
    typedef ORebindPointer<tPointer,const tKey> const_pointer;

    typedef tKey value_type;
    typedef tKey key_type;
    typedef tKey& reference;
    typedef const tKey& const_reference;
    typedef std::ptrdiff_t difference_type;
    typedef std::size_t size_type;
    typedef tCompare value_compare;
    typedef tCompare key_compare;

    class SHook
    {
        typedef detail::CRBTreeNode<pointer> tNode;

        tNode mNode;

        friend tNode &get_rbtree_node_from_key(SHook &pHook)    {   return pHook.mNode; }
    };

    class SCompactHook
    {
        typedef detail::CRBTreeCompactNode<pointer> tNode;
        
        tNode mNode;

        friend tNode &get_rbtree_node_from_key(SCompactHook &pHook)    {   return pHook.mNode; }
    };

private:
    struct SData : public detail::CSizeHolder<vConstTimeSize,size_type>,
                   public UMemberAsBase<tCompare>
    {
        SData(const tCompare &pComp)
            :   UMemberAsBase<tCompare>(pComp)
            ,   mRoot(nullptr)
            ,   mMin(nullptr)
            ,   mMax(nullptr)
        {
            this->SetSize(0);
        }
        
        SData(SData &&pRH)
            :   detail::CSizeHolder<vConstTimeSize,size_type>(pRH)
            ,   UMemberAsBase<tCompare>(std::move(pRH))
            ,   mRoot(pRH.mRoot)
            ,   mMin(pRH.mMin)
            ,   mMax(pRH.mMax)
        {}

        pointer mRoot;
        pointer mMin;
        pointer mMax;
    };

    template<bool pConst>
    class SIterator : public IFacade<SIterator<pConst>,std::bidirectional_iterator_tag,
                                     typename std::conditional<pConst,const tKey,tKey>::type>
    {
        friend class IFacade<SIterator<pConst>,std::bidirectional_iterator_tag,
                                     typename std::conditional<pConst,const tKey,tKey>::type>;
        typedef typename std::conditional<pConst,const_reference,reference>::type TReference;

    public:
        /// default constructor

        /// leaves the iterator in a non-deferenceable, non-incrementable, non-comparable state
        SIterator()
            :   mNode(nullptr)
            ,   mTree(nullptr)
        {}

        SIterator(const SIterator<false> &pNonConstIt)
            :   mNode(pNonConstIt.mNode)
            ,   mTree(pNonConstIt.mTree)
        {}

    private:
        /// initializes the iterator from a \c tValue
        SIterator(pointer pNode,tTreePointer pTree)
            :   mNode(pNode)
            ,   mTree(pTree)
        {}

        /// returns the current value of the counter.
        TReference Dereference() const
        {
            return *mNode;
        }

        /// increments the value of the iterator
        void Increment()
        {
            mNode=mTree->NextNode(mNode);
        }

        /// decrements the value of the iterator
        void Decrement()
        {
            mNode=mTree->PrevNode(mNode);
        }

        /// returns true if the two iterators contain the same value
        bool Equal(const SIterator &pO) const
        {
            return mNode==pO.mNode;
        }

        pointer mNode;
        tTreePointer mTree;

        template<bool>
        friend class SIterator;
        friend class CIntrusiveRBTree;
    };

    template<bool pConst>
    friend class SIterator;

public:
     typedef SIterator<false> iterator;
     typedef SIterator<true> const_iterator;
     typedef std::reverse_iterator<iterator> reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

public:
    /// constructs an empty tree

    /// \throws nothing except if the copy constructor of \p tCompare throws
    CIntrusiveRBTree(const tCompare &pComp=tCompare())
        :   mData(pComp)
    {}

    /// constructs an empty tree and inserts elements from [\p pB, \p pE)

    /// \requires Dereferencing iterator must yield an lvalue of type value_type.
    /// \c pComp must be a comparison function that induces a strict weak ordering.
    ///
    /// \complexity Linear in \c N if [\p pB, \p pE) is already sorted using
    /// \c pComp and otherwise N * log N, where N is the distance between first and last.
    ///
    /// \throws nothing except if the copy constructor of \p tCompare throws
    template<typename tIt>
    CIntrusiveRBTree(bool pUnique,tIt pB,tIt pE,const tCompare &pComp=tCompare())
        :   mData(pComp)
    {
        if(pUnique)
            InsertUnique(pB,pE);
        else
            InsertEqual(pB,pE);
    }
    
    /// move constructor
    CIntrusiveRBTree(CIntrusiveRBTree &&pRH)
        :   mData(std::move(pRH))
    {}

    /// destructor

    /// Doesn't delete the objects in the tree, i.e. no destructor is called
    ~CIntrusiveRBTree()
    {}

    /// returns an \c iterator pointing to the beginning of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    iterator begin()
    {
        return iterator(mData.mMin,this);
    }

    /// returns a \c const_iterator pointing to the beginning of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_iterator begin() const
    {
        return cbegin();
    }

    /// returns a \c const_iterator pointing to the beginning of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_iterator cbegin() const
    {
        return const_iterator(mData.mMin,this);
    }

    /// returns an \c iterator pointing to the end of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    iterator end()
    {
        return iterator(nullptr,this);
    }

    /// returns a \c const_iterator pointing to the end of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_iterator end() const
    {
        return cend();
    }

    /// returns a \c const_iterator pointing to the end of the tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_iterator cend() const
    {
        return const_iterator(nullptr,this);
    }

    /// returns a \c reverse_iterator pointing to the beginning of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    /// returns a \c const_reverse_iterator pointing to the beginning of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_reverse_iterator rbegin() const
    {
        return reverse_iterator(end());
    }

    /// returns a \c const_reverse_iterator pointing to the beginning of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_reverse_iterator crbegin()
    {
        return const_reverse_iterator(end());
    }

    /// returns a \c reverse_iterator pointing to the end of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    /// returns a \c const_reverse_iterator pointing to the end of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_reverse_iterator rend() const
    {
        return reverse_iterator(begin());
    }

    /// returns a \c const_reverse_iterator pointing to the end of the reverse tree.

    /// \complexity constant
    ///
    /// \throws nothing
    const_reverse_iterator crend()
    {
        return const_reverse_iterator(begin());
    }

    /// returns \c true if the container is empty

    /// \complexity constant
    ///
    /// \throws nothing
    bool empty() const
    {
        return !mData.mRoot;
    }

    /// returns the number of elements stored in the tree

    /// \complexity constant if vConstTimeSize is true. Linear with the number of elements
    ///             in the container otherwise
    ///
    /// \throws nothing
    size_type size() const
    {
        if(vConstTimeSize)
            return mData.GetSize();
        else
            return std::distance(begin(),end());
    }

    /// inserts \p pValue into the tree

    /// \complexity average complexity is at most logarithmic
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    iterator InsertEqual(reference pValue)
    {
        pointer lToInsert(&pValue);
        DoInsert(lToInsert,GetUpperBoundInsert(pValue));
        return iterator(lToInsert,this);
    }

    /// inserts \p pValue into the tree, using \p pHint as a hint as to where to insert it

    /// \param pHint must be a valid iterator. It should be an upper bound for the insertion.
    ///
    /// \complexity logarithmic in general, amortized constant time if \p pValue is inserted immediately
    ///             before \p pHint
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    /// \todo actually use \p pHint
    iterator InsertEqual(const_iterator /*pHint*/, reference pValue)
    {
        ///\todo
        return InsertEqual(pValue);
    }

    /// inserts each element in the range [\p pB, \p pE) into the tree

    /// \param pHint must be a valid iterator. It should be an upper bound for the insertion.
    ///
    /// \complexity N * log(N) in general, where N is the size of the range. However, it is linear in
    ///             N if the range is already sorted
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    template<class tIt>
    void InsertEqual(tIt pB, tIt pE)
    {
        for(;pB!=pE;++pB)
            InsertEqual(*pB);
    }

    /// inserts \p pValue into the tree if it isn't already present

    /// \complexity average complexity is at most logarithmic
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    std::pair<iterator,bool> InsertUnique(reference pValue)
    {
        auto lPair=GetLowerBoundInsert(pValue);
        const tCompare &lComp=mData.GetMember();
        if(lPair.first&&!lComp(pValue,*lPair.first))
            return {iterator(lPair.first,this),false};
        pointer lToInsert(&pValue);
        DoInsert(lToInsert,lPair);
        return {iterator(lToInsert,this),true};
    }

    /// inserts \p pValue into the tree if it isn't already present, using \p pHint as a hint as to where to insert it

    /// \param pHint must be a valid iterator. It should be an upper bound for the insertion.
    ///
    /// \complexity logarithmic in general, amortized constant time if \p pValue is inserted immediately
    ///             before \p pHint
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    std::pair<iterator,bool> InsertUnique(const_iterator /*pHint*/,reference pValue)
    {
        ///\todo use hint
        return InsertUnique(pValue);
    }

    /// inserts each element in the range [\p pB, \p pE) into the tree that is not already present

    /// \param pHint must be a valid iterator. It should be an upper bound for the insertion.
    ///
    /// \complexity N * log(N) in general, where N is the size of the range. However, it is linear in
    ///             N if the range is already sorted
    ///
    /// \throws nothing except if the \c tCompare function throws
    ///
    /// \note does not affect the validity of iterators and references. No copy constructors are called.
    template<class tIt>
    void InsertUnique(tIt pB,tIt pE)
    {
        for(;pB!=pE;++pB)
            InsertUnique(*pB);
    }

    //! <b>Effects</b>: Erases the element pointed to by pos.
    //!
    //! <b>Complexity</b>: Average complexity for erase element is constant time.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Note</b>: Invalidates the iterators (but not the references)
    //!    to the erased elements. No destructors are called.
    iterator erase(const_iterator pI)
    {
        iterator lRet(NextNode(pI.mNode),this);
        DoErase(pI.mNode);
        return lRet;
    }

    //! <b>Effects</b>: Erases the range pointed to by b end e.
    //!
    //! <b>Complexity</b>: Average complexity for erase range is at most
    //!   O(log(size() + N)), where N is the number of elements in the range.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Note</b>: Invalidates the iterators (but not the references)
    //!    to the erased elements. No destructors are called.
    iterator erase(const_iterator pB, const_iterator pE)
    {
        while(pB!=pE)
        {
            pointer lNode=pB.mNode;
            ++pB;
            DoErase(lNode);
        }
        return iterator(pB.mNode,this);
    }


    //! <b>Effects</b>: Erases all the elements with the given value.
    //!
    //! <b>Returns</b>: The number of erased elements.
    //!
    //! <b>Complexity</b>: O(log(size() + N).
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Note</b>: Invalidates the iterators (but not the references)
    //!    to the erased elements. No destructors are called.
    size_type erase(const_reference pValue)
    {
        auto lRange=equal_range(pValue);
        size_type lRet=0;
        while(lRange.first!=lRange.second)
        {
            pointer lNode=lRange.first.mNode;
            ++lRange.first;
            DoErase(lNode);
            ++lRet;
        }
        return lRet;
    }

    //! <b>Effects</b>: Erases all of the elements.
    //!
    //! <b>Complexity</b>: Linear to the number of elements on the container.
    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
    //!
    //! <b>Throws</b>: Nothing.
    //!
    //! <b>Note</b>: Invalidates the iterators (but not the references)
    //!    to the erased elements. No destructors are called.
    void clear()
    {
        mData.mRoot=nullptr;
        mData.mMin=nullptr;
        mData.mMax=nullptr;
        mData.SetSize(0);
    }

    //! <b>Effects</b>: Returns the number of contained elements with the given value
    //!
    //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
    //!   to number of objects with the given value.
    //!
    //! <b>Throws</b>: Nothing.
    size_type count(const_reference pValue) const
    {
        auto lEqual=equal_range(pValue);
        return std::distance(lEqual.first,lEqual.second);
    }

    //! <b>Effects</b>: Returns an iterator to the first element whose
    //!   key is not less than k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    iterator lower_bound(const_reference pValue)
    {
        return iterator(GetLowerBound(pValue),this);
    }

    //! <b>Effects</b>: Returns an iterator to the first element whose
    //!   key is not less than k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    const_iterator lower_bound(const_reference pValue) const
    {
        return const_iterator(GetLowerBound(pValue),this);
    }

    //! <b>Effects</b>: Returns an iterator to the first element whose
    //!   key is greater than k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    iterator upper_bound(const_reference pValue)
    {
        return iterator(GetUpperBound(pValue),this);
    }

    //! <b>Effects</b>: Returns an iterator to the first element whose
    //!   key is greater than k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    const_iterator upper_bound(const_reference pValue) const
    {
        return const_iterator(GetUpperBound(pValue),this);
    }

    //! <b>Effects</b>: Finds an iterator to the first element whose key is
    //!   k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    iterator find(const_reference pValue)
    {
        pointer lNode=GetLowerBound(pValue);
        const tCompare &lComp=mData.GetMember();
        return (!lNode||lComp(pValue,*lNode))?end():iterator(lNode,this);
    }

    //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
    //!   k or end() if that element does not exist.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    const_iterator find(const_reference pValue) const
    {
        pointer lNode=GetLowerBound(pValue);
        const tCompare &lComp=mData.GetMember();
        return (!lNode||lComp(pValue,*lNode))?cend():const_iterator(lNode,this);
    }

    //! <b>Effects</b>: Finds a range containing all elements whose key is k or
    //!   an empty range that indicates the position where those elements would be
    //!   if they there is no elements with key k.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    std::pair<iterator,iterator> equal_range(const_reference pValue)
    {
        std::pair<pointer,pointer> lRange=GetEqualRange(pValue);
        return {iterator(lRange.first,this),iterator(lRange.second,this)};
    }

    //! <b>Effects</b>: Finds a range containing all elements whose key is k or
    //!   an empty range that indicates the position where those elements would be
    //!   if they there is no elements with key k.
    //!
    //! <b>Complexity</b>: Logarithmic.
    //!
    //! <b>Throws</b>: Nothing.
    std::pair<const_iterator,const_iterator> equal_range(const_reference pValue) const
    {
        std::pair<pointer,pointer> lRange=GetEqualRange(pValue);
        return {const_iterator(lRange.first,this),const_iterator(lRange.second,this)};
    }

    //! <b>Requires</b>: value must be an lvalue and shall be in a set of
    //!   appropriate type. Otherwise the behavior is undefined.
    //!
    //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
    //!   that points to the value
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Throws</b>: Nothing.
    iterator iterator_to(reference pValue)
    {
        return iterator(pointer(&pValue),this);
    }

    //! <b>Requires</b>: value must be an lvalue and shall be in a set of
    //!   appropriate type. Otherwise the behavior is undefined.
    //!
    //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
    //!   set that points to the value
    //!
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Throws</b>: Nothing.
    const_iterator iterator_to(const_reference pValue) const
    {
        return const_iterator(pointer(&pValue),this);
    }

private:
    pointer GetParent(const pointer &pKey) const
    {
        return get_rbtree_node_from_key(*pKey).GetParent();
    }

    pointer GetLeft(const pointer &pKey) const
    {
        return get_rbtree_node_from_key(*pKey).GetLeft();
    }

    pointer GetRight(const pointer &pKey) const
    {
        return get_rbtree_node_from_key(*pKey).GetRight();
    }

    bool GetRed(const pointer &pKey) const
    {
        return get_rbtree_node_from_key(*pKey).GetRed();
    }

    void SetParent(const pointer &pKey,const pointer &pParent)
    {
        get_rbtree_node_from_key(*pKey).SetParent(pParent);
    }

    void SetLeft(const pointer &pKey,const pointer &pLeft)
    {
        get_rbtree_node_from_key(*pKey).SetLeft(pLeft);
    }

    void SetRight(const pointer &pKey,const pointer &pRight)
    {
        get_rbtree_node_from_key(*pKey).SetRight(pRight);
    }

    void SetRed(const pointer &pKey,bool pRed)
    {
        get_rbtree_node_from_key(*pKey).SetRed(pRed);
    }

    void InitNode(const pointer &pKey,const pointer &pParent,bool pRed)
    {
        get_rbtree_node_from_key(*pKey).Init(pParent,pRed);
    }

    void RotateLeft(pointer pNode)
    {
        pointer lOldParent=GetParent(pNode);

        pointer lX=GetRight(pNode);
        pointer lXLeft=GetLeft(lX);
        SetRight(pNode,lXLeft);
        if(lXLeft)
            SetParent(lXLeft,pNode);
        SetLeft(lX,pNode);
        SetParent(pNode,lX);
        SetParent(lX,lOldParent);
        if(lOldParent)
        {
            if(pNode==GetLeft(lOldParent))
                SetLeft(lOldParent,lX);
            else
                SetRight(lOldParent,lX);
        }
        else
            mData.mRoot=lX;
    }

    void RotateRight(pointer pNode)
    {
        pointer lOldParent=GetParent(pNode);

        pointer lX=GetLeft(pNode);
        pointer lXRight=GetRight(lX);
        SetLeft(pNode,lXRight);
        if(lXRight)
            SetParent(lXRight,pNode);
        SetRight(lX,pNode);
        SetParent(pNode,lX);
        SetParent(lX,lOldParent);
        if(lOldParent)
        {
            if(pNode==GetLeft(lOldParent))
                SetLeft(lOldParent,lX);
            else
                SetRight(lOldParent,lX);
        }
        else
            mData.mRoot=lX;
    }

    void DoInsert(pointer pNode,const std::pair<pointer,pointer> &pWhere)
    {
        mData.IncrementSize();

        if(!pWhere.second) //this will only happen if the tree is empty
        {
            InitNode(pNode,nullptr,false);
            mData.mRoot=pNode;
            mData.mMin=pNode;
            mData.mMax=pNode;
            return;
        }
        else if(pWhere.first==pWhere.second) //insert as a left child
        {
            InitNode(pNode,pWhere.second,true);
            SetLeft(pWhere.second,pNode);
            if(pWhere.second==mData.mMin)
                mData.mMin=pNode;
        }
        else //insert as a right child
        {
            InitNode(pNode,pWhere.second,true);
            SetRight(pWhere.second,pNode);
            if(pWhere.second==mData.mMax)
                mData.mMax=pNode;
        }

        while(pNode!=mData.mRoot&&GetRed(GetParent(pNode)))
        {
            pointer lParent=GetParent(pNode);
            pointer lParentParent=GetParent(lParent);

            if(GetLeft(lParentParent)==lParent)
            {
                pointer lX=GetRight(lParentParent);
                if(lX&&GetRed(lX))
                {
                    SetRed(lParent,false);
                    SetRed(lParentParent,true);
                    SetRed(lX,false);
                    pNode=lParentParent;
                }
                else
                {
                    if(GetRight(lParent)==pNode)
                    {
                        pNode=lParent;
                        RotateLeft(pNode);
                    }
                    pointer lNewParent=GetParent(pNode);
                    pointer lNewParentParent=GetParent(lNewParent);
                    SetRed(lNewParent,false);
                    SetRed(lNewParentParent,true);
                    RotateRight(lNewParentParent);
                }
            }
            else
            {
                pointer lX=GetLeft(lParentParent);
                if(lX&&GetRed(lX))
                {
                    SetRed(lParent,false);
                    SetRed(lParentParent,true);
                    SetRed(lX,false);
                    pNode=lParentParent;
                }
                else
                {
                    if(GetLeft(lParent)==pNode)
                    {
                        pNode=lParent;
                        RotateRight(pNode);
                    }
                    pointer lNewParent=GetParent(pNode);
                    pointer lNewParentParent=GetParent(lNewParent);
                    SetRed(lNewParent,false);
                    SetRed(lNewParentParent,true);
                    RotateLeft(lNewParentParent);
                }
            }
        }

        SetRed(mData.mRoot,false);
    }

    void ReplaceInParent(pointer pNode,pointer pWith)
    {
        pointer lParent=GetParent(pNode);
        if(!lParent)
            mData.mRoot=pWith;
        else if(GetLeft(lParent)==pNode)
            SetLeft(lParent,pWith);
        else
            SetRight(lParent,pWith);
    }
    
    void DoErase(pointer pNode)
    {
        mData.DecrementSize();
        
        pointer lX;
        pointer lXParent(nullptr);
        pointer lLeft(GetLeft(pNode));
        pointer lRight(GetRight(pNode));

        if(!lLeft)
        {
            ReplaceInParent(pNode,lRight);
            if(lRight)
            {
                if(mData.mMin==pNode)
                    mData.mMin=Minimum(lRight);
                SetParent(lRight,GetParent(pNode));
            }
            else
            {
                if(mData.mMin==pNode)
                    mData.mMin=GetParent(pNode);
                if(mData.mMax==pNode)
                    mData.mMax=GetParent(pNode);
            }
            lX=lRight;
            lXParent=GetParent(pNode);
        }
        else if(!lRight)
        {
            if(mData.mMax==pNode)
                mData.mMax=Maximum(lLeft);
            ReplaceInParent(pNode,lLeft);
            SetParent(lLeft,GetParent(pNode));
            lX=lLeft;
            lXParent=GetParent(pNode);
        }
        else //it has right and left nodes
        {
            pointer lY=Minimum(lRight);
            lX=GetRight(lY);

            SetParent(GetLeft(pNode),lY);
            SetLeft(lY,GetLeft(pNode));
 
            if(lY!=GetRight(pNode))
            {
                lXParent=GetParent(lY);
                if(lX)
                    SetParent(lX,lXParent);
                SetLeft(lXParent,lX);
                SetRight(lY,GetRight(pNode));
                SetParent(GetRight(pNode),lY);
            }
            else
            {
                lXParent=lY;
            }
            ReplaceInParent(pNode,lY);
            SetParent(lY,GetParent(pNode));
            bool lRed=GetRed(lY);
            SetRed(lY,GetRed(pNode));
            SetRed(pNode,lRed);
        }

        if(!GetRed(pNode))
        {
            while(lX!=mData.mRoot&&(!lX||!GetRed(lX)))
            {
                if(lX==GetLeft(lXParent))
                {
                    pointer lW=GetRight(lXParent);
                    if(GetRed(lW))
                    {
                        SetRed(lW,false);
                        SetRed(lXParent,true);
                        RotateLeft(lXParent);
                        lW=GetRight(lXParent);
                    }
                    if((!GetLeft(lW)||!GetRed(GetLeft(lW)))&&
                       (!GetRight(lW)||!GetRed(GetRight(lW))))
                    {
                        SetRed(lW,true);
                        lX=lXParent;
                        lXParent=GetParent(lXParent);
                    }
                    else
                    {
                        if(!GetRight(lW)||!GetRed(GetRight(lW)))
                        {
                            SetRed(GetLeft(lW),false);
                            SetRed(lW,true);
                            RotateRight(lW);
                            lW=GetRight(lXParent);
                        }
                        SetRed(lW,GetRed(lXParent));
                        SetRed(lXParent,false);
                        if(GetRight(lW))
                            SetRed(GetRight(lW),false);
                        RotateLeft(lXParent);
                        break;
                    }
                }
                else
                {
                    pointer lW=GetLeft(lXParent);
                    if(GetRed(lW))
                    {
                        SetRed(lW,false);
                        SetRed(lXParent,true);
                        RotateRight(lXParent);
                        lW=GetLeft(lXParent);
                    }
                    if((!GetLeft(lW)||!GetRed(GetLeft(lW)))&&
                       (!GetRight(lW)||!GetRed(GetRight(lW))))
                    {
                        SetRed(lW,true);
                        lX=lXParent;
                        lXParent=GetParent(lXParent);
                    }
                    else
                    {
                        if(!GetLeft(lW)||!GetRed(GetLeft(lW)))
                        {
                            SetRed(GetRight(lW),false);
                            SetRed(lW,true);
                            RotateLeft(lW);
                            lW=GetLeft(lXParent);
                        }
                        SetRed(lW,GetRed(lXParent));
                        SetRed(lXParent,false);
                        if(GetLeft(lW))
                            SetRed(GetLeft(lW),false);
                        RotateRight(lXParent);
                        break;
                    }
                }
            }
            if(lX)
            {
                SetRed(lX,false);
            }
        }
    }
    
    pointer Minimum(pointer pNode) const
    {
        for(pointer lLeft=GetLeft(pNode);lLeft;lLeft=GetLeft(pNode))
            pNode=lLeft;
        return pNode;
    }

    pointer Maximum(pointer pNode) const
    {
        for(pointer lRight=GetRight(pNode);lRight;lRight=GetRight(pNode))
            pNode=lRight;
        return pNode;
    }

    pointer NextNode(pointer pNode) const
    {
        if(pointer lRight=GetRight(pNode))
            return Minimum(lRight);

        for(pointer lX=GetParent(pNode);lX;lX=GetParent(lX))
        {
            if(pNode==GetLeft(lX))
                return lX;
            pNode=lX;
        }

        return nullptr;
    }

    pointer PrevNode(pointer pNode) const
    {
        if(!pNode)
            return mData.mMax;

        if(pointer lLeft=GetLeft(pNode))
            return Maximum(lLeft);

        for(pointer lX=GetParent(pNode);lX;lX=GetParent(lX))
        {
            if(pNode==GetRight(lX))
                return lX;
            pNode=lX;
        }

        return nullptr;
    }

    /// calculates the upper bound for \p pKey in the tree

    /// \return a pair of two node pointers. The \c first element in the pair is the true upper bound, i.e. the first
    /// element that is greater than \p pKey. The \c second element represents the insertion point, i.e. the parent
    /// for an insertion of \p pKey. If \c first==second then it should be inserted as a left child of \c second,
    /// otherwise as a right child
    std::pair<pointer,pointer> GetUpperBoundInsert(const_reference pKey) const
    {
        if(!mData.mRoot) return {nullptr,nullptr};

        pointer lY(nullptr);
        pointer lX(mData.mRoot);

        const tCompare &lComp=mData.GetMember();

        while(true)
        {
            if(lComp(pKey,*lX))
            {
                lY=lX;
                lX=GetLeft(lX);
                if(!lX)
                    return {lY,lY};
            }
            else
            {
                if(!GetRight(lX))
                    return {lY,lX};
                lX=GetRight(lX);
            }
        }
    }

    /// calculates the lower bound for \p pKey in the tree

    /// \return a pair of two node pointers. The \c first element in the pair is the true lower bound, i.e. the first
    /// element that is greater or equal than \p pKey. The \c second element represents the insertion point, i.e.
    /// the parent for an insertion of \p pKey. If \c first==second then it should be inserted as a left child of
    /// \c second, otherwise as a right child
    std::pair<pointer,pointer> GetLowerBoundInsert(const_reference pKey) const
    {
        pointer lY(nullptr);
        pointer lX(mData.mRoot);

        const tCompare &lComp=mData.GetMember();

        if(!lX) return {lY,lY};

        while(true)
        {
            if(lComp(*lX,pKey))
            {
                if(!GetRight(lX))
                    return {lY,lX};
                lX=GetRight(lX);
            }
            else
            {
                lY=lX;
                lX=GetLeft(lX);
                if(!lX)
                    return {lY,lY};
            }
        }
    }

    pointer GetLowerBound(const_reference pKey) const
    {
        pointer lY(nullptr);
        pointer lX(mData.mRoot);

        const tCompare &lComp=mData.GetMember();

        while(lX)
        {
            if(lComp(*lX,pKey))
            {
                lX=GetRight(lX);
            }
            else
            {
                lY=lX;
                lX=GetLeft(lX);
            }
        }

        return lY;
    }

    pointer GetUpperBound(const_reference pKey) const
    {
        pointer lY(nullptr);
        pointer lX(mData.mRoot);

        const tCompare &lComp=mData.GetMember();

        while(lX)
        {
            if(lComp(pKey,*lX))
            {
                lY=lX;
                lX=GetLeft(lX);
            }
            else
            {
                lX=GetRight(lX);
            }
        }

        return lY;
    }

    std::pair<pointer,pointer> GetEqualRange(const_reference pKey) const
    {
        pointer lY(nullptr);
        pointer lX(mData.mRoot);

        const tCompare &lComp=mData.GetMember();

        while(lX)
        {
            if(lComp(*lX,pKey))
            {
                lX=GetRight(lX);
            }
            else if(lComp(pKey,*lX))
            {
                lY=lX;
                lX=GetLeft(lX);
            }
            else
            {
                pointer lXU(lX),lYU(lY);
                lY=lX;
                lX=GetLeft(lX);
                lXU=GetRight(lXU);

                while(lX)
                {
                    if(lComp(*lX,pKey))
                    {
                        lX=GetRight(lX);
                    }
                    else
                    {
                        lY=lX;
                        lX=GetLeft(lX);
                    }
                }

                while(lXU)
                {
                    if(lComp(pKey,*lXU))
                    {
                        lYU=lXU;
                        lXU=GetLeft(lXU);
                    }
                    else
                    {
                        lXU=GetRight(lXU);
                    }
                }
                return {lY,lYU};
            }
        }
        return {lY,lY};
    }

public:
    void CheckBalance(pointer pNode=nullptr,int pBlacks=0,int pNumBlacks=-1)
    {
        if(!pNode)
        {
            if(mData.mRoot)
            {
                if(GetRed(mData.mRoot))
                {
                    msg_error() << "root is not black\n";
                }
                CheckBalance(mData.mRoot);
            }
        }
        else
        {
            if(GetRed(pNode))
            {
                if(GetRed(GetParent(pNode)))
                {
                    msg_error() << pNode->mIndex << "\n";
                    msg_error() << GetParent(pNode)->mIndex << "\n";
                    msg_error() << "violated color constraint in rbtree!!\n";
                }
            }
            else
            {
                pBlacks++;
            }
            
            if(pointer lLeft=GetLeft(pNode))
            {
                if(GetParent(lLeft)!=pNode)
                    msg_error() << "wrong parent in node\n";
                CheckBalance(lLeft,pBlacks,pNumBlacks);
            }
            else
            {
                if(pNumBlacks<0)
                    pNumBlacks=pBlacks;
                else if(pNumBlacks!=pBlacks)
                    msg_error() << "unbalanced rb tree!!\n";
            }

            if(pointer lRight=GetRight(pNode))
            {
                if(GetParent(lRight)!=pNode)
                    msg_error() << "wrong parent in node\n";
                CheckBalance(lRight,pBlacks,pNumBlacks);
            }
            else
            {
                if(pNumBlacks<0)
                    pNumBlacks=pBlacks;
                else if(pNumBlacks!=pBlacks)
                    msg_error() << "unbalanced rb tree!!\n";
            }
        }
    }

    void CheckOrder()
    {
        if(!mData.mRoot)
        {
            if(mData.mMin||mData.mMax)
            {
                msg_error() << "order problem: wrong mMin or mMax\n";
                return;
            }
        }

        if(mData.mMin!=Minimum(mData.mRoot))
        {
            msg_error() << "order problem: wrong mMin\n";
        }

        if(mData.mMax!=Maximum(mData.mRoot))
        {
            msg_error() << "order problem: wrong mMax\n";
        }

        const tCompare &lComp=mData.GetMember();

        int lSize=1;
        for(pointer lX=mData.mMin;lX!=mData.mMax;)
        {
            if(!GetParent(lX)&&lX!=mData.mRoot)
            {
                msg_error() << "order problem: no parent, no root\n";
            }
            else if(GetParent(lX))
            {
                if(lX!=GetLeft(GetParent(lX))&&lX!=GetRight(GetParent(lX)))
                    msg_error() << "order problem: is not a child of parent\n";
            }
            lSize++;
            pointer lNext=NextNode(lX);
            if(lComp(*lNext,*lX))
            {
                msg_error() << "order problem: wrong order\n";
                return;
            }
            lX=lNext;
        }

        if(lSize!=size())
        {
            msg_error() << "order problem: wrong size " << lSize << "!=" << size() << "\n";
        }
    }

private:
    SData mData;
};

/*namespace buola*/ }

#endif
